/* Set tab stop to 1 */
/*-----------------------------------------------------------------------------
 * File Name ..... util.c
 *
 * Purpose ....... Contains utility functions
 *
 * Functions ..... ceil_log2, MyMalloc, MyCalloc, GetNewSortedItems,
 *					  intcmp, Get_Nth_Bit_From_Right, Merge, PrintIntArray
 *					  limit_rand, ConvertToFract, PH_Merge, PH_GetNewSortedItems
 *					  PrintPHArray, pos_limit_rand
 *
 * Date Written .. April 28, 1993
 *
 * Modification History
 *	 Author				Date								  Purpose
 *	 ------				----								  -------
 * Sagar Sawant		 April 28, 1993			The original version of util.c
 * Sagar Sawant		 Oct	27, 1993			Added the function PH_Merge,
 *														 PH_GetNewSortedItems, PrintPHArray
	* Sagar Sawant		 Feb	10, 1994			Added mergemin & mergemax
 *---------------------------------------------------------------------------*/


/*------------------------------ Include Files ------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <pthread.h>
#include <limits.h>
#include "pardef.h"
#include "parheap.h"
#include "think.h"
#include "exp_inc.h"
#ifdef USE_SSE
#include <xmmintrin.h>
#endif

/*------------------------------ # defines ----------------------------------*/
#define RAND_LIMIT 99

/*------------------------------- Functions ---------------------------------*/
int ParHeapCmp(const void *elem1, const void *elem2);
int ceil_log2();
void *MyMalloc(int MemSize);
void *MyCalloc(int MemSize);
/* int *GetNewSortedItems(); */
void PH_GetNewSortedItems(int n, int startelem, long  maxvalue, PARHEAP *ParItems);
int intcmp();
void counting_sort(PARHEAP array[], int n);
int Get_Nth_Bit_From_Right();
/* void Merge(); */
void PH_Merge(PARHEAP* array1,int size1, PARHEAP *array2, int size2, PARHEAP *MergeArray);
void PrintIntArray();
void PrintPHArray();
int pos_limit_rand();
int limit_rand();
double ConvertToFract(int num);
void CopyPHItems(PARHEAP *A, PARHEAP *B);
/* externs */
extern int exp_inc();
extern int MAX_THINK_TIME;
extern int think(int);
extern PARHEAP *** ParHeap;
extern PARHEAP *DeletedItems;



/*----------------------------------------------------------------------------
 * Function ........... ceil_log2
 *
 * Purpose ............ Calculates the ceiling of log n to the base 2.
 *
 * Arguments Passed ... n - number whose log is to be calculated
 *
 * Return Value ....... log n to the base 2
 *
 * Globals Modified ... None
 *---------------------------------------------------------------------------*/
int ceil_log2(n)
int n;
{
    return (int) ceil( (log10( (double) n) / log10(2.0)) );
}


/*----------------------------------------------------------------------------
 * Function ........... MyMalloc
 *
 * Purpose ............ Allocates memory using malloc and does error checking
 *
 * Arguments Passed ... MemSize - size of memory to be allocated
 *
 * Return Value ....... Pointer to the allocated memory
 *
 * Globals Modified ... None
 *---------------------------------------------------------------------------*/
void *MyMalloc(int MemSize)
{
    void *ptr;

    if ( (ptr = (void *) malloc(MemSize)) == (void *) NULL)
    {
        fprintf(stderr, "Error (MyMalloc) : Unable to allocate memory\n");
        exit(0);
    }
    return ptr;
}


/*----------------------------------------------------------------------------
 * Function ........... MyCalloc
 *
 * Purpose ............ Allocates memory using calloc (for 1 element only)
 *							 and does error checking
 *
 * Arguments Passed ... MemSize - size of memory to be allocated
 *
 * Return Value ....... Pointer to the allocated memory
 *
 * Globals Modified ... None
 *---------------------------------------------------------------------------*/
void *MyCalloc(int MemSize)
{
    void *ptr;

    if ( (ptr = (void *) calloc(1, MemSize)) == (void *) NULL)
    {
        fprintf(stderr, "Error (MyCalloc) : Unable to allocate memory\n");
        exit(0);
    }
    return ptr;
}


/*----------------------------------------------------------------------------
 * Function ........... GetSortedInsertItems
 *
 * Purpose ............ Returns an array of r random sorted integers
 *
 * Arguments Passed ... n - size of array to be returned
 *							 limit - limit on the values of the integers
 *							 Items - array of sorted integers
 *
 * Return Value ....... None
 *
 * Globals Modified ... None
 *---------------------------------------------------------------------------*/
/********* Not being used anywhere
void GetSortedInsertItems(n, limit, Items)
int n;
int limit;
int *Items;
{
	int i;
	unsigned tmp;

	if (n == 0)
		return;

	for ( i=0 ; i<n ; i++)
		Items[i] = limit_rand(limit-1) + 1;
	qsort(Items, n, sizeof(int), intcmp);

	fprintf(stderr, "GetSortedInsertItems : Items are\n");
	PrintIntArray(stderr, Items, n);
	fprintf(stderr, "\n");
}
**********/

/*----------------------------------------------------------------------------
 * Function ........... PH_GetNewSortedItems
 *
 * Purpose ............ Returns an array of r random sorted PARHEAP items.
 *
 * Arguments Passed ... n - size of array to be returned
 *						 limit - limit on the values of the integers
 *
 * Return Value ....... Pointer to the sorted array.
 *
 * Globals Modified ... None
 *---------------------------------------------------------------------------*/
void PH_GetNewSortedItems(int n, int startelem, long  maxvalue, PARHEAP *ParItems)
{
    int	i;
    if (n <= 0)
        return;
    for ( i=0 ; i<n ; i++)
    {
        if (startelem != USE_RANDOM_DATA)
        {
            ParItems[i].item = DeletedItems[startelem+i].item + exp_inc();
            think(MAX_THINK_TIME);
        }
        else
        {
            ParItems[i].item = (int)(rand() % maxvalue);
        }
    }
    //qsort(ParItems, n, sizeof(int), ParHeapCmp);
    counting_sort(ParItems, n);

    /* for ( i=0 ; i<n ; i++ )
    {
       ParItems[i].item = Items[i].item;
    }
    */
    //memcpy(ParItems, Items, n * sizeof(PARHEAP)); /* This is correct if PARHEAP Size = int size */
    }

/*----------------------------------------------------------------------------
 * Function ........... pos_limit_rand
 *
 * Purpose ............ Returns a positive random number less or equal to the
 *							 specified limit
 *
 * Arguments Passed ... limit
 *
 * Return Value ....... The random number
 *
 * Globals Modified ... None
 *---------------------------------------------------------------------------*/
int pos_limit_rand(int limit)
{
    return ((rand() % limit) + 1);
}


/*----------------------------------------------------------------------------
 * Function ........... limit_rand
 *
 * Purpose ............ Returns a random number less or equal to the
 *							 specified limit
 *
 * Arguments Passed ... limit
 *
 * Return Value ....... The random number
 *
 * Globals Modified ... None
 *---------------------------------------------------------------------------*/
int limit_rand(limit)
int limit;
{
    int num;

    num = rand();
    if (num > limit)
        return (num % (limit+1));
    else
        return num;
}


/*----------------------------------------------------------------------------
 * Function ........... ConvertToFract
 *
 * Purpose ............ Converts the integer to a fraction by succesively
 *							 dividing it by 10 till its value is less than 1.
 *
 * Arguments Passed ... num - number to be converted to a fraction
 *
 * Return Value ....... The fraction
 *
 * Globals Modified ... None
 *---------------------------------------------------------------------------*/
double ConvertToFract(int num)
{
    double d_num = num;

    while (d_num > 1)
        d_num = d_num / 10;
    return d_num;
}


/*----------------------------------------------------------------------------
 * Function ........... intcmp
 *
 * Purpose ............ Integer comparison function required by qsort(). Its
 *							 functionality is similar to strcpy().
 *
 * Arguments Passed ... int1, int2 - pointers to the 2 integers to be compared.
 *
 * Return Value ....... -1 : if int1 < int2
 *							  0 : if int1 = int2
 *							  1 : if int1 > int2
 *
 * Globals Modified ... None
 *---------------------------------------------------------------------------*/
int intcmp(int1, int2)
int *int1;
int *int2;
{
    if (*int1 < *int2)
        return -1;
    else
        return (*int1 > *int2);
}


void counting_sort(PARHEAP array[], int n)
{
    int min, max;
    int i = 0, j = 0, z = 0;
    int range;
    int *count;

    min = max = array[0].item;
    for (i = 0; i < n; i++)
    {
        if (array[i].item > max)
             max = array[i].item;
        else if (array[i].item < min)
             min = array[i].item;
    }

    range = max - min + 1;
    count = (int*)MyCalloc(range * sizeof(int));

    for (i = 0; i < n; i++)
    {
        count[ array[i].item - min ] += 1;
    }

    for (i = min; i <= max; i++)
    {
        for (j = 0; j < count[i - min]; j++)
        {
            array[z].item = i;
            z += 1;

        }

    }
    free(count);
}

/*----------------------------------------------------------------------------
 * Function ........... Get_Nth_Bit_From_Right
 *
 * Purpose ............ Isn't that obvious from the name itself?
 *
 * Arguments Passed ... num - number whose nth bit it required
 *							 n
 *
 * Return Value ....... the nth bit from right of num
 *
 * Globals Modified ... None
 *---------------------------------------------------------------------------*/
int Get_Nth_Bit_From_Right(num, n)
int num;
int n;
{
    unsigned bit;

    bit = (unsigned) num;
    bit >>= n-1;
    return (int) (bit & 1);
}


/*----------------------------------------------------------------------------
 * Function ........... PH_Merge
 *
 * Purpose ............ Merges array1 and array2 into MergeArray. ALL THREE
 *							 ARRAYS CONTAIN PARHEAP STRUCTURES. This algorithm
 *							 can be made more efficient by using sentinels
 *							 as end markers for array1 and array2. However that
 *							 would require appending markers to array1 and array2
 *							 and strictly this function should not modify array1 and
 *							 array2. Hence 2 extra comparisons are carried out to
 *							 check end of array1 and array2.
 *
 * Arguments Passed ... array1 - 1st array
 *							 size1 - size of 1st array
 *							 array2 - 2nd array
 *							 size2 - size of 2nd array
 *							 MergeArray - target array (assumed to be allocated)
 *											  This is called by reference.
 *
 * Return Value ....... None
 *
 * Globals Modified ... None
 *---------------------------------------------------------------------------*/
void PH_Merge(PARHEAP* array1,int size1, PARHEAP *array2, int size2, PARHEAP *MergeArray)
{
    int i=0, j=0, k, TotSize;

    if (size1 == 0)			 /* if 1st array empty, just copy from 2nd array */
    {
        memcpy(MergeArray, array2, size2*sizeof(PARHEAP) );
        return;
    }
    else if (size2 == 0)
    {
        memcpy(MergeArray, array1, size1*sizeof(PARHEAP) );
        return;
    }
    TotSize = size1 + size2;

    for (k=0 ; (i<size1) && (j< size2) ; k++)
    {
        if (array1[i].item < array2[j].item)
        {
            CopyPHItems(&(MergeArray[k]), &(array1[i]));
            i++;
        }
        else
        {
            CopyPHItems(&MergeArray[k], &array2[j]);
            j++;
        }
    }
    if (i >= size1)			 /* if 1st array over, just copy from 2nd array */
        memcpy(&MergeArray[k], &array2[j], (TotSize-k)*sizeof(PARHEAP) );
    else
        memcpy(&MergeArray[k], &array1[i], (TotSize-k)*sizeof(PARHEAP) );
}

/*----------------------------------------------------------------------------
 * Function ........... PrintIntArray
 *
 * Purpose ............ Prints an array of integers
 *
 * Arguments Passed ... outfile - the print file
 *							 Array - the array to be printed
 *							 ArraySize - the size of the array
 *
 * Return Value ....... None
 *
 * Globals Modified ... None
 *---------------------------------------------------------------------------*/
void PrintIntArray(outfile, Array, ArraySize)
FILE *outfile;
int *Array;
int ArraySize;
{
    int i;

    fprintf(outfile, "[ ");
    for ( i=0 ; i<ArraySize ; i++)
        fprintf(outfile, "%d ", Array[i]);
    fprintf(outfile, "]");
}


/*----------------------------------------------------------------------------
 * Function ........... PrintPHArray
 *
 * Purpose ............ Prints an array of PARHEAP items
 *
 * Arguments Passed ... outfile - the print file
 *							 Array - the array to be printed
 *							 ArraySize - the size of the array
 *
 * Return Value ....... None
 *
 * Globals Modified ... None
 *---------------------------------------------------------------------------*/
void PrintPHArray(outfile, Array, ArraySize)
FILE *outfile;
PARHEAP *Array;
int ArraySize;
{
    int i;
    fprintf(outfile, "[ ");
    for ( i=0 ; i<ArraySize ; i++)
        fprintf(outfile, "%d ", Array[i].item);
    fprintf(outfile, "]");
}


/*----------------------------------------------------------------------------
 * Function ........... CopyPHItems
 *
 * Purpose ............ Copies structure B into structure A
 *
 * Arguments Passed ... A, B
 *
 * Return Value ....... None
 *
 * Globals Modified ... None
 *---------------------------------------------------------------------------*/
void CopyPHItems(PARHEAP *A, PARHEAP *B)
{
    A->item = B->item;
    /*
    			A->from = B->from;
    			A->to = B->to;
    			A->status = B->status;
    			A->id = B->id;
    */
}


/*-----------------------------------------------------------------------------
	 A = min r of A+B
	 C = max r of A+B
 *---------------------------------------------------------------------------*/
void mergemin (PARHEAP * A, int r, PARHEAP * B, int s, PARHEAP * C)
{
    int indexA = r-1, indexB = s-1, indexC = s-1;
    /* fill C right to left */
    for ( ; indexC >= 0 ; indexC-- )
    {
        if ( A[indexA].item > B[indexB].item )
        {
            CopyPHItems(&C[indexC], &A[indexA]);
            indexA--;
        }
        else
        {
            CopyPHItems(&C[indexC], &B[indexB]);
            indexB--;
        }
    }
    indexC = r-1;	 /* reuse indexC to index into A right to left */

    /* fill A right to left */
    while ( indexB >= 0 )
    {
        if (indexA < 0)
            break;
        if ( A[indexA].item > B[indexB].item )
        {
            CopyPHItems(&A[indexC], &A[indexA]);
            indexA--;
        }
        else
        {
            CopyPHItems(&A[indexC], &B[indexB]);
            indexB--;
        }
        indexC--;
    }
    if (indexA < 0)
        memcpy(A, B, (indexC+1)*sizeof(PARHEAP));
}


/*-----------------------------------------------------------------------------
	 B = max r of A+B
	 C = min r of A+B
 *---------------------------------------------------------------------------*/
void mergemax (PARHEAP * A, PARHEAP * B, PARHEAP * C, int r)
{
    int indexA = 0, indexB = 0, indexC = 0;

    /* fill C left to right */
    for ( ; indexC < r ; indexC++ )
        if ( A[indexA].item < B[indexB].item )
        {
            CopyPHItems(&C[indexC], &A[indexA]);
            indexA++;
        }
        else
        {
            CopyPHItems(&C[indexC], &B[indexB]);
            indexB++;
        }

    indexC = 0;	 /* reuse indexC to index into B left to right */

    /* fill B left to right */
    while ( indexA < r )
    {
        if (indexB >= r)
            break;
        if ( A[indexA].item < B[indexB].item )
        {
            CopyPHItems(&B[indexC], &A[indexA]);
            indexA++;
        }
        else
        {
            CopyPHItems(&B[indexC], &B[indexB]);
            indexB++;
        }
        indexC++;
    }
    if (indexB >= r) 
        memcpy(B, A, (r-indexC)*sizeof(PARHEAP));
}

int ParHeapCmp(const void *elem1, const void *elem2)
{
    PARHEAP *e1, *e2;
    e1 = (PARHEAP *) elem1;
    e2 = (PARHEAP *) elem2;
    if (e1->item < e2->item)
        return -1;
    else
        return (e1->item > e2->item);
}


